//动态规划
class Solution 
{
public:
    int wiggleMaxLength(vector<int>& nums) 
    {
        int n=nums.size();
        int ret=1;
        //状态表示以i结尾的摆动序列长度最大值
        vector<int>f(n,1);//到i是上升的
        vector<int>g(n,1);//到i是下降的
        for(int i=1;i<n;i++)
        {
            int tem1=0;
            int tem2=0;
            for(int j=0;j<i;j++)
            {
               if(nums[j]<nums[i])
               {
                tem2=max(g[j],tem2);
               }
               else if(nums[j]>nums[i])
               {
                tem1=max(tem1,f[j]);
               }
               else
               {
                tem1=tem2=0;
               }
            }
            f[i]=max(tem2+1,f[i]);
            g[i]=max(tem1+1,g[i]);
            ret=max(max(f[i],g[i]),ret);
        }
        return ret;
    }
};


class Solution 
{
public:
    int wiggleMaxLength(vector<int>& nums) 
    {
       int left=0;//代表此时便利位置左边的排定状态
       int right=0;//代表此时便利位置左边的排定状态
       //0代表此时状态平或者两者都有可能
       //-1:下降 1：上升
        int ret=0;
        int n=nums.size();
        for(int i=0;i<n-1;i++)
        {
            right=nums[i+1]-nums[i];
            if(right==0) continue;
            //初始我们的第一个元素左边的增减情况都有可能 此时右侧无论为何止都要记录答案
            if(left*right<=0)
            {
                ret++;
            }
            left=right;
        }
        //最后一个加1是因为我们循环中没有考虑遍历到最后一个位置情况
        return ret+1;
    }

};